(a) Field of the Invention
The present invention relates to a low density parity check (LDPC) encoding method. More particularly, the present invention relates to a block LDPC encoding method and an apparatus thereof.
(b) Description of the Related Art
As mobile communication systems develop, the need to develop techniques for efficiently transmitting large capacity data in a wired/wireless network is increasing. Accordingly, in the mobile communication system, an error-control code is used as a method for improving system performance by efficiently reducing data loss caused by noise, interference, or a fading effect in a channel.
For the error-control code, a turbo code and an LDPC code are widely used. The LDPC code may be appropriately used since performance of the LDPC code is similar to that of the turbo code, it has lower complexity than that of the turbo code, and it is easy to parallelize. In addition, excellent performance to the Shannon limit may be achieved when a code length increases, which has been actively studied to be applied to a next generation mobile communication system.
A basic configuration of the LDPC code is defined by a parity check matrix. The parity check matrix is defined as a sparse configuration in which many elements of the parity check matrix respectively have a 0 value, and remaining elements thereof have non-zero values. An (N,j,k) LDPC code is a linear block code, which has a block length of N, j elements having non-zero values for each column and k elements having values of 1 for each row.
In this case, the number of elements having non-zero values for each column or each row in the parity check matrix is referred to as a weight, an LDPC code having regular weights of each column and each row is referred to as a regular LDPC code, and an LDPC code having irregular weights of each column and each row is referred to as an irregular LDPC code. Generally, the irregular LDPC code has better performance compared to the regular LDPC code. However, in the irregular LDPC code, since the parity check matrix has irregular weights of each column and each row, the weights are required to be appropriately adjusted to guarantee excellent performance.
FIG. 1 is a diagram representing a parity check matrix of a conventional LDPC code, and FIG. 2 is a factor graph of the LDPC code using the parity check matrix shown in FIG. 1.
As shown in FIG. 1, a parity check matrix H of an (8, 2, 4) LDPC code is used to decode the LDPC code, the parity check matrix H includes 8 columns and 4 rows, and weights are regularly formed such that a weight of each column is 2 and a weight of each row is 4. Since the weights are regularly formed for each column and each row in the parity check matrix, the (8, 2, 4) LDPC code shown in FIG. 1 is the regular LDPC code.
FIG. 2 is a diagram representing a factor graph of the (8, 2, 4) LDPC code.
Referring to FIG. 2, the factor graph of the (8, 2, 4) LDPC code includes 8 variable nodes (x1, x2, x3, x4, x5, x6, x7, and x8) and 4 check nodes (s16, s18, s10, and s12). Performance of the LDPC code increases as the number of edges that connect the variable nodes and the check nodes increases. Since it is required to calculate a generator matrix G from the parity check matrix to perform an encoding operation, it is difficult to generate the generator matrix when the code length increases and the size of the parity check matrix increases.
To solve the above problem, a block LDPC code has been developed to efficiently perform the encoding operation of the LDPC code without reducing performance. In the block LDPC code, the generator matrix is not calculated in the parity check matrix, the parity check matrix is appropriately divided, and the encoding operation is directly performed by using the divided matrix.
FIG. 3 is a diagram representing the parity check matrix of a conventional block LDPC code, and FIG. 4 and FIG. 5 are diagrams representing superscript matrixes of a partial matrix of the parity check matrix of the block LDPC code shown in FIG. 3.
In the block LDPC code, an efficient encoding operation, an efficient operation for storing the parity check matrix, and performance improvement are considered.
As shown in FIG. 3, in the parity check matrix H that is the block LDPC code, the entire parity check matrix is divided into a plurality of partial blocks, and permutation matrixes correspond to respective divided blocks.
Hereinafter, the permutation matrix corresponding to the partial matrix will be referred to as a “partial matrix”. w denotes a permutation matrix having a size of z×z, it is a zero matrix when a value thereof is −1, and it is an unitary matrix having the size of z×z when the value thereof is 0. When the value is a number that is greater than 0, the unitary matrix having the size of z×z is cyclically shifted by the value to form the permutation matrix. A superscript Hb of the permutation matrix w is given as shown in FIG. 4 and FIG. 5.
In addition, mb indicates that the corresponding permutation matrix is positioned in an mbth row among the plurality of partial blocks of the parity check matrix, and nb indicates that the corresponding permutation matrix is positioned in an nbth column among the plurality of partial blocks of the parity check matrix. That is, Wmbnb indicates a permutation matrix positioned in a partial block at a crossing region of the mbth row and nbth column of the parity check matrix including the plurality of partial blocks.
In addition, since the number of all rows is z×mb and the number of all columns is z×nb in the entire parity check matrix of the LDPC code shown in FIG. 3, when the entire parity check matrix of the block LDPC code has a full rank, a coding rate may be shown as Equation 1 regardless of the size of the partial blocks.
                    R        =                                                            z                ×                                  n                  b                                            -                              z                ×                                  m                  b                                                                    z              ×                              n                b                                              =                                                                      n                  b                                -                                  m                  b                                                            n                b                                      =                          1              -                                                m                  b                                                  n                  b                                                                                        [                  Equation          ⁢                                          ⁢          1                ]            
The entire LDPC parity check matrix has a size of z(mb×nb). However, the entire LDPC parity check matrix may be expressed by using mb×nb superscripts, and therefore the size of a memory for storing all parity check matrix information is reduced to be 1/z.
In addition, the LDPC parity check matrix has a unique configuration to perform an efficient encoding operation. The LDPC code is used to generate a parity check bit having a size of z×nb−z×mb based on input data formed in an information block type having a length of z×mb, and the entire codeword has a size of z×nb formed by adding a parity check block to the information block, and is transmitted.
FIG. 6 is a diagram representing the codeword of the block LDPC code divided into partial blocks including an information block u, a first parity block p1, and a second parity block p2.
Here, the information block is a part of the parity check matrix mapped to actual information in a process for encoding the block LDPC code. In addition, the first and second parity blocks are a part of the parity check matrix mapped to an actual parity in the operation for encoding the block LDPC code, and are formed by dividing a parity part into two parts.
FIG. 7 is a diagram representing 6 partial blocks divided from the parity check matrix according to a structural characteristic of the block LDPC code.
Referring to FIG. 7, the parity check matrix of the block LDPC code shown in FIG. 6 is divided into an information part and a parity part, and it includes a partial block A and partial block C included in the information part, a partial block B and a partial block D included in a first parity part, and a partial block T and a partial block E included in a second parity part. Here, the information part is a part of the party check matrix to which an actual information vector (an information block) is mapped in the process for encoding the block LDPC code. The parity part is a part of the parity check matrix mapped to the actual parity block in the process for encoding to the block LDPC code, and it is divided into two parts.
Relationships between the parity check matrix and codeword blocks may be given as Equation 2.AuT+Bp1T+Tp2T=0CuT+Dp1T+Ep2T=0  [Equation 2]
An equation for calculating a parity block as given in Equation 3 may be obtained from Equation 2.p2T=T−1(AuT+Bp1T)p1T=(ET−1B+D)−1(ET−1A+C)uT  [Equation 3]
In the block LDPC encoding operation, ET−1B+D is formed to be an unitary matrix, and T−1 is easily calculated in Equation 3 so as to efficiently realize the LDPC encoding operation. Therefore, Equation 3 may be simplified as Equation 4.p2T=T−1AuT+T−1Bp1T p1T=ET−1AuT+CuT  [Equation 4]
When the information block and the parity block are divided into blocks having sizes of z (hereinafter referred to as an “information unit block”) as shown in FIG. 6, a product of a partial block forming the LDPC parity check matrix without 0 is a value obtained by cyclically shifting the information unit block having the size of z by a shift weight of the partial block. A product of the partial block and the information block according to the shift weight value is given as Equation 5 when z is 4. As shown in Equation 5, a value obtained by cyclically shifting the information block by the weight value is the same as a value obtained by multiplying the information block by the partial block that is cyclically shifted by the shift weight.
                                                                                                              [                                                                                            1                                                                          0                                                                          0                                                                          0                                                                                                                      0                                                                          1                                                                          0                                                                          0                                                                                                                      0                                                                          0                                                                          1                                                                          0                                                                                                                      0                                                                          0                                                                          0                                                                          1                                                                                      ]                                    ⁡                                      [                                                                                                                        u                            1                                                                                                                                                                            u                            2                                                                                                                                                                            u                            3                                                                                                                                                                            u                            4                                                                                                                ]                                                  =                                  [                                                                                                              u                          1                                                                                                                                                              u                          2                                                                                                                                                              u                          3                                                                                                                                                              u                          4                                                                                                      ]                                                            p                0                                                                                                                              [                                                                                            0                                                                          1                                                                          0                                                                          0                                                                                                                      0                                                                          0                                                                          1                                                                          0                                                                                                                      0                                                                          0                                                                          0                                                                          1                                                                                                                      1                                                                          0                                                                          0                                                                          0                                                                                      ]                                    ⁡                                      [                                                                                                                        u                            1                                                                                                                                                                            u                            2                                                                                                                                                                            u                            3                                                                                                                                                                            u                            4                                                                                                                ]                                                  =                                  [                                                                                                              u                          2                                                                                                                                                              u                          3                                                                                                                                                              u                          4                                                                                                                                                              u                          1                                                                                                      ]                                                            p                1                                                                                                                                                                    [                                                                                                    0                                                                                0                                                                                1                                                                                0                                                                                                                                0                                                                                0                                                                                0                                                                                1                                                                                                                                1                                                                                0                                                                                0                                                                                0                                                                                                                                0                                                                                1                                                                                0                                                                                0                                                                                              ]                                        ⁡                                          [                                                                                                                                  u                              1                                                                                                                                                                                          u                              2                                                                                                                                                                                          u                              3                                                                                                                                                                                          u                              4                                                                                                                          ]                                                        =                                      [                                                                                                                        u                            3                                                                                                                                                                            u                            4                                                                                                                                                                            u                            1                                                                                                                                                                            u                            2                                                                                                                ]                                                  ⁢                                                                                              p                2                                                                                                                              [                                                                                            0                                                                          0                                                                          0                                                                          1                                                                                                                      1                                                                          0                                                                          0                                                                          0                                                                                                                      0                                                                          1                                                                          0                                                                          0                                                                                                                      0                                                                          0                                                                          1                                                                          0                                                                                      ]                                    ⁡                                      [                                                                                                                        u                            1                                                                                                                                                                            u                            2                                                                                                                                                                            u                            3                                                                                                                                                                            u                            4                                                                                                                ]                                                  =                                  [                                                                                                              u                          4                                                                                                                                                              u                          1                                                                                                                                                              u                          2                                                                                                                                                              u                          3                                                                                                      ]                                                            p                3                                                                        [                  Equation          ⁢                                          ⁢          5                )            
It is well known that the above block LDPC code and the turbo code have an excellent performance gain in high-rate data transmission, and the block LDPC code has a merit in that an error caused by a noise generated in a transmission channel is efficiently corrected and reliability of data transmission may be increased. However, to process high-capacity data including high quality motion picture data in real time in a developed mobile communication system, it is required to minimize complexity so that the high capacity data may be quickly processed in the conventional LDPC encoding operation. In addition, it is required to reduce capacity of a memory required to realize the conventional block LDPC encoding operation, to reduce hardware complexity and to reduce manufacturing cost.
The above information disclosed in this Background section is only for enhancement of understanding of the background of the invention and therefore it may contain information that does not form the prior art that is already known in this country to a person of ordinary skill in the art.